/*
 * @lc app=leetcode.cn id=714 lang=swift
 *
 * [714] 买卖股票的最佳时机含手续费
 */

// @lc code=start
class Solution {
    func maxProfit(_ prices: [Int], _ fee: Int) -> Int {
        let n = prices.count
        if n < 2 { return 0 }
        var dp = Array(repeating: Array(repeating: 0, count: 2), count: n)
        for i in 0..<n {
            if i == 0 {
                dp[i][0] = 0
                dp[i][1] = -prices[i]
                continue
            }
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]-fee)
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
        }
        return dp[n-1][0]
    }
}
// @lc code=end

